1. Field of the Invention
This invention relates to priority encoders.
2. Prior Art
The basic logic function of a priority encoder is to scan a number of parallel input lines or the bits of a digital word for the active line or bit with the highest priority. The input lines or bits of a digital word are ranked in order of priority from the highest to the lowest. All of the input lines or bits are scanned by a priority encoder to determine which of the input lines or bits are active. Then, the priority encoder provides an output code word which identifies the line number or bit of the highest priority active input line or bit.
One important application of priority encoder is to scan the interrupt request lines in a computer system for the highest-priority request. Another application is to arbitrate and to prioritize allocation of the various resources in a computer system, which has a number of prioritized users.
Certain priority-encoder applications require scanning either a very large number of input lines or a very large number of bits of a digital word. Various schemes are available for expanding basic priority-encoder integrated circuit designs to handle larger numbers of input lines or bits. Specific applications requiring a large number of input bits are in the fields of pattern recognition and database management. Pattern recognition is used for analysis of images, speech patterns, and acoustics. For pattern recognition applications, the width of a large data word depends on the specific type of data being analyzed. For image analysis, the data words may be hundreds of bits in length, while in speech analysis, the data words may be 48 bits, or even as short as 16 bits. For database management applications, the length of a data word is determined by the number of characters in a data string. Even within the same database management system, the data word may be either fixed in length or variable in length depending on the type of data being handled. Consequently, it is expected that a priority encoder design should be able to accommodate the requirement that the length of a data word can vary from system to system as well as from application to application within one system.
Discrete integrated-circuit priority encoders, such as the SN54/74S148 and SN54/74S348, provided by Advanced Micro Devices, Inc. of Sunnyvale, Calif., priority-encode eight input request lines into a 3-bit binary code word, which is provided at the output terminals. To provide for expansion by cascading of these integrated-circuit encoders, three control signals are provided, which include an enable input signal EI, an enable output signal EO, and a group select signal GS. These priority encoders internally use combinatorial logic gates to select the highest-priority input line. To accommodate a greater number of input lines, several of these priority encoders are cascaded using the EI, EO, and GS signals. For example, to accommodate 64 input lines, 8 of these 8-input-integrated circuit priority encoders are used to receive the 64 input lines. To provide a second level of logic, an additional integrated-circuit priority encoder is used. The combinatorial logic circuits of these types of integrated circuits consume large amounts of chip area.
The Advanced Micro Devices, Inc. AM99C 10 content-addressable-memory CAM internally incorporates a 256 input-line priority encoder, which uses a combinatorial logic circuit design similar to that of the SN54/74S148 design. A considerable amount of chip area could be saved if a simpler 256 input-line priority encoder design were available to replace combinatorial logic designs for priority encoders.